Backdrop

백준 온라인 저지 ▸ 17218

비밀번호 만들기
IV

문제

최근 들어 개인정보 유출에 대한 뉴스를 많이 본 수형이는 한 사이트의 비밀번호가 유출 되더라도 다른 사이트에서 똑같은 비밀번호로 접속할 수 없도록 사이트마다 비밀번호를 다르게 설정하기로 다짐했다. 많이 고민한 결과 수형이는 눈을 감고 키보드를 막 쳐서 나온 두 문자열에서 공통으로 존재하는 가장 긴 부분 문자열을 비밀번호로 하기로 하였다. 수형이가 눈을 감고 만든 두 문자열이 주어졌을 때 비밀번호를 만드는 프로그램을 만들어보자.

입력

첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 최대 40자이다. 빈 문자열은 주어지지 않는다. 가장 긴 부분 문자열은 반드시 하나만 존재한다.

출력

첫 번째 줄에 입력으로 주어진 두 문자열로 만든 비밀번호를 출력한다.

예제 입력 1

AUTABBEHNSA
BCUAMEFKAJNA

예제 출력 1

UAENA

AUTABBEHNSA
BCUAMEFKAJNA\

예제 입력 2

SETAPPLE
EATMANY

예제 출력 2

ETA

SETAPPLE
EATMANY

풀이

python

코드

a = input()
b = input()
 
prev = None
curr = [""] * len(b)
for i in range(len(a)):
    prev = curr[:]
    for j in range(len(b)):
        if a[i] == b[j]:
            curr[j] = (prev[j - 1] if j else "") + a[i]
        else:
            top = prev[j]
            left = curr[j - 1] if j else ""
            if len(top) > len(left):
                curr[j] = top
            else:
                curr[j] = left
 
print(curr[-1])